Routers are devices that direct traffic in a network. Each router in the network has a route table that typically includes routing information to enable incoming packets to be forwarded or routed to their destination in the network. Some routers forward packets based only on the destination address indicated in the packet. Other, more complex, routers forward or route packets based on policies defined, for example, by a network administrator. The latter routing schemes are commonly referred to as policy-based routing.
Policy-based routing can enable packets to be forwarded or routed in a network based on any number of criteria, including the source of the packet, the destination of the packet, the cost of forwarding the packet through different routes or paths in the network, or the bandwidth available on different routes in the network. Policy-based routing can also be used to provide a certain Quality of Service (QoS) or Type of Service (ToS) to differentiated traffic in the network. For example, one or more of the various fields (e.g., the ToS bits) in the header of an Internet Protocol (IP) packet can be used by policy-based routers to forward IP packets in a network.
Each policy-based router implements a policy through the use of route maps that define how to forward the packet in the network. Each route map statement or policy statement is referred to herein as a rule and contains one or more match clauses and a set clause. The match clauses are a series of conditions that are used to determine if an incoming packet satisfies a particular rule. If the rule is satisfied, the set clause specifies how the router should forward the packet in the network. If none of the match clauses of a given rule is satisfied, the policy-based router investigates lower priority rules.
A content addressable memory (CAM) may be used within a policy-based router to determine whether an incoming packet matches a rule. In a typical implementation, each rule is converted to one or more match clauses that are stored within respective entries in the CAM. When an incoming packet is received, it is processed by control circuitry within the router (e.g., typically a host processor and/or network processor) to determine the policy field information. The policy field information, in turn, is provided to the CAM as a policy search key. For each match clause in the CAM that matches the policy search key, a corresponding match signal is asserted, thereby enabling the host processor to determine if a given rule is satisfied.
Entries stored within a CAM are often prioritized according to storage location. For example, in a conventional CAM, entries stored at lower-numbered addresses are typically deemed to have a higher priority than entries stored at higher-numbered addresses. This presents challenges in policy-based routers, as it is often necessary to insert new rules having intermediate priorities (or higher priorities) relative to previously stored rules. For example, if a CAM device contains N rules having priorities ranging from a highest priority (0) to a lowest priority (N−1), and a new rule having a higher priority than the existing rules is to be stored, then each of the existing N rules is deleted from its current location and stored again at a lower priority location to make room for the new rule to be stored in the highest priority location. Such operation tends to be time consuming and inefficient both for the control circuitry within the router (e.g., typically a host processor and/or network processor) and the CAM.